In many multi-agent settings, participants can form teams to achieve collective outcomes that may far surpass their individual capabilities.

The core is a central solution concept in cooperative game theory, defined as the set of feasible allocations or payments such that no subset of agents has incentive to break away and form their own subgroup or coalition. However, it has long been known that the core (and approximations, such as the least-core) are hard to compute. This limits our ability to analyze cooperative games in general, and to fully embrace cooperative game theory contributions in domains such as explainable AI (XAI), where the core can complement the Shapley values to identify influential features or instances supporting predictions by black-box models. We propose novel iterative algorithms for computing variants of the core, which avoid the computational bottleneck of many other approaches; namely solving large linear programs. As such, they scale better to very large problems as we demonstrate across different classes of cooperative games, including weighted voting games, induced subgraph games, and marginal contribution networks. We also explore our algorithms in the context of XAI, providing further evidence of the power of the core for such applications.

In many multi-agent settings, participants can form teams to achieve collective outcomes that may far surpass their individual capabilities. Measuring the relative contributions of agents and allocating them shares of the reward that promote long-lasting cooperation are difficult tasks. Cooperative game theory offers solution concepts identifying distribution schemes, such as the Shapley value, that fairly reflect the contribution of individuals to the performance of the team or the Core, which reduces the incentive of agents to abandon their team. Applications of such methods include identifying influential features and sharing the costs of joint ventures or team formation. Unfortunately, using these solutions requires tackling a computational barrier as they are hard to compute, even in restricted settings. In this work, we show how cooperative game-theoretic solutions can be distilled into a learned model by training neural networks to propose fair and stable payoff allocations. We show that our approach creates models that can generalize to games far from the training distribution and can predict solutions for more players than observed during training. An important application of our framework is Explainable AI: our approach can be used to speed-up Shapley value computations on many instances.

Weighted voting games apply to a wide variety of multi-agent settings. They enable the formalization of power indices which quantify the coalitional power of players. We take a novel approach to the study of the power of big vs. small players in these games. We model small (big) players as having single (multiple) votes. The aggregate relative power of big players is measured w.r.t. their votes proportion. For this ratio, we show small constant worst-case bounds for the Shapley-Shubik and the Deegan-Packel indices. In sharp contrast, this ratio is unbounded for the Banzhaf index. As an application, we define a false-name strategic normal form game where each big player may split its votes between false identities, and study its various properties. Together, our results provide foundations for the implications of players’ size, modeled as their ability to split, on their relative power.

Weighted voting games is one of the most important classes of cooperative games. Recently, Zhang and Grossi [53] proposed a variant of this class, called delegative simple games, which is well suited to analyse the relative importance of each voter in liquid democracy elections. Moreover, they defined a power index, called the delagative Banzhaf index to compute the importance of each agent (i.e., both voters and delegators) in a delegation graph based on two key parameters: the total voting weight she has accumulated and the structure of supports she receives from her delegators. We obtain several results related to delegative simple games. We first propose a pseudo-polynomial time algorithm to compute the delegative Banzhaf and Shapley-Shubik values in delegative simple games. We then investigate a bribery problem where the goal is to maximize/minimize the voting power/weight of a given voter in a delegation graph by changing at most a fixed number of delegations. We show that the problems of minimizing/maximizing a voter's power index value are strongly NP-hard. Furthermore, we prove that having a better approximation guarantee than $1-1/e$ to maximize the voting weight of a voter is not possible, unless $P = NP$, then we provide some parameterized complexity results for this problem. Finally, we show that finding a delegation graph with a given number of gurus that maximizes the minimum power index value an agent can have is a computationally hard problem.

A key issue in cooperative game theory is coalitional stability, usually captured by the notion of the core---the set of outcomes that are resistant to group deviations. However, some coalitional games have empty cores, and any outcome in such a game is unstable. We investigate the possibility of stabilizing a coalitional game by using subsidies. We consider scenarios where an external party that is interested in having the players work together offers a supplemental payment to the grand coalition, or, more generally, a particular coalition structure. This payment is conditional on players not deviating from this coalition structure, and may be divided among the players in any way they wish. We define the cost of stability as the minimum external payment that stabilizes the game. We provide tight bounds on the cost of stability, both for games where the coalitional values are nonnegative (profit-sharing games) and for games where the coalitional values are nonpositive (cost-sharing games), under natural assumptions on the characteristic function, such as superadditivity, anonymity, or both. We also investigate the relationship between the cost of stability and several variants of the least core. Finally, we study the computational complexity of problems related to the cost of stability, with a focus on weighted voting games.

Predictive modeling applications increasingly use data representing people's behavior, opinions, and interactions. Fine-grained behavior data often has different structure from traditional data, being very high-dimensional and sparse. Models built from these data are quite difficult to interpret, since they contain many thousands or even many millions of features. Listing features with large model coefficients is not sufficient, because the model coefficients do not incorporate information on feature presence, which is key when analysing sparse data. In this paper we introduce two alternatives for explaining predictive models by listing important features. We evaluate these alternatives in terms of explanation "bang for the buck,", i.e., how many examples' inferences are explained for a given number of features listed. The bottom line: (i) The proposed alternatives have double the bang-for-the-buck as compared to just listing the high-coefficient features, and (ii) interestingly, although they come from different sources and motivations, the two new alternatives provide strikingly similar rankings of important features.

Weighted voting games allow for studying the distribution of power between agents in situations of collective decision making. While the conventional version of these games assumes that any agent is always ready to cooperate with all others, recently, more involved models have been proposed, where cooperation is subject to restrictions. Following Myerson [1977], such restrictions are typically represented by a graph that expresses available communication links among agents. In this paper, we study the time complexity of computing two well-known power indices - the Shapley-Shubik index and the Banzhaf index - in the graph-restricted weighted voting games. We show that both are #P-complete and propose a dedicated dynamic-programming algorithm that runs in pseudo-polynomial time for graphs with the bounded treewidth.

False-name manipulation refers to the question of whether a player in a weighted voting game can increase her power by splitting into several players and distributing her weight among these false identities. Relatedly, the beneficial merging problem asks whether a coalition of players can increase their power in a weighted voting game by merging their weights. For the problems of whether merging or splitting players in weighted voting games is beneficial in terms of the Shapley--Shubik and the normalized Banzhaf index, merely NP-hardness lower bounds are known, leaving the question about their exact complexity open. For the Shapley--Shubik and the probabilistic Banzhaf index, we raise these lower bounds to hardness for PP, "probabilistic polynomial time," a class considered to be by far a larger class than NP. For both power indices, we provide matching upper bounds for beneficial merging and, whenever the new players' weights are given, also for beneficial splitting, thus resolving previous conjectures in the affirmative. Relatedly, we consider the beneficial annexation problem, asking whether a single player can increase her power by taking over other players' weights. It is known that annexation is never disadvantageous for the Shapley--Shubik index, and that beneficial annexation is NP-hard for the normalized Banzhaf index. We show that annexation is never disadvantageous for the probabilistic Banzhaf index either, and for both the Shapley--Shubik index and the probabilistic Banzhaf index we show that it is NP-complete to decide whether annexing another player is advantageous. Moreover, we propose a general framework for merging and splitting that can be applied to different classes and representations of games.